package com.codebuffer.nowcoder;

import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.concurrent.LinkedBlockingDeque;


public class SolutionZ {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        Deque<TreeNode> deque1 = new LinkedBlockingDeque();
        Deque<TreeNode> deque2 = new LinkedBlockingDeque();

        ArrayList list = new ArrayList();
        if(null==pRoot){
            return list;
        }
        deque1.add(pRoot);

        int i = 0;
        while(deque1.size()>0 || deque2.size()>0){
            i++;
            List<Integer> listN = new ArrayList<>();
            Deque<TreeNode> deque11 = deque1.size()>0?deque1:deque2;
            Deque<TreeNode> deque22 = deque1.size()>0?deque2:deque1;

            while(deque11.size()>0){
                TreeNode treeNode;
                if (i%2==0){
                    treeNode = deque11.pollLast();
                }else {
                    treeNode = deque11.pollFirst();
                }

                listN.add(treeNode.val);
                if(i%2==0){
                    if(null!=treeNode.left){
                        deque22.addLast(treeNode.left);
                    }
                    if(null!=treeNode.right){
                        deque22.addLast(treeNode.right);
                    }
                }else {
                    if(null!=treeNode.right){
                        deque22.addFirst(treeNode.right);
                    }
                    if(null!=treeNode.left){
                        deque22.addFirst(treeNode.left);
                    }
                }

            }
            list.add(listN);

        }


        return list;
    }

}
